//
//  QuickSort.swift
//  Sorts
//
//  Created by lhc on 2023/12/17.
//

import Foundation


/// 单路快速排序
class QuickSortOneWays: QuickSort {
    
    fileprivate override func partition(left: Int, right: Int) -> Int {
        randomSelectV(left: left, right: right)
        
        let v = array[left]
        var i = left + 1
        var j = left
        
        while i <= right {
            if array[i] < v {
                j += 1
                execute(a: i, b: j)
                exchange(a: i, b: j)
            }
            i += 1
        }
        execute(a: left, b: j)
        exchange(a: left, b: j)
        return j
    }
}

/// 双路快速排序
class QuickSortTwoWays: QuickSort {
    fileprivate override func partition(left: Int, right: Int) -> Int {
        randomSelectV(left: left, right: right)
        
        let v = array[left]
        var i = left + 1
        var j = right
        
        while true {
            while i <= j && array[i] < v {
                i += 1
            }
            
            while i <= j && array[j] > v {
                j -= 1
            }
            
            if i >= j {break}
            
            execute(a: i, b: j)
            exchange(a: i, b: j)
            i += 1
            j -= 1
        }
        
        execute(a: left, b: j)
        exchange(a: left, b: j)
        return j
    }
}

/// 三路快速排序
class QuickSortThreeWays: QuickSort {
    override func sortByRecursion(left: Int, right: Int) {
        if left >= right {
            return
        }
        let (lessThan, greatThan) = partitionThreeWays(left: left, right: right)
        sortByRecursion(left: left, right: lessThan)
        sortByRecursion(left: greatThan, right: right)
    }
    
    private func partitionThreeWays(left: Int, right: Int) -> (Int, Int) {
        randomSelectV(left: left, right: right)
        
        let v = array[left]
        
        var i = left + 1
        var lessThan = left
        var greatThan = right + 1
        
        while i < greatThan {
            if array[i] < v {
                lessThan += 1
                execute(a: lessThan, b: i)
                exchange(a: lessThan, b: i)
                i += 1
            }else if array[i] == v {
                i += 1
            }else if array[i] > v {
                greatThan -= 1
                execute(a: greatThan, b: i)
                exchange(a: greatThan, b: i)
            }
        }
        
        execute(a: left, b: lessThan)
        exchange(a: left, b: lessThan)
        lessThan -= 1
        return (lessThan, greatThan)
    }
}


class QuickSort: BaseSort {
    
    var action: ((OperatorType, (Int, Int)) -> ())?
    
    
    func sort() {
        self.sortByRecursion(left: 0, right: self.array.count - 1)
    }
    
    fileprivate func sortByRecursion(left: Int, right: Int) {
        if left >= right {
            return
        }
        
        let j = partition(left: left, right: right)
        sortByRecursion(left: left, right: j - 1)
        sortByRecursion(left: j + 1, right: right)
    }
    
    fileprivate func partition(left: Int, right: Int) -> Int {
        return 0
    }
    
    fileprivate func randomSelectV(left: Int, right: Int) {
        let randomIndex = Int.random(in: left...right)
        if randomIndex != left {
            execute(a: left, b: randomIndex)
            exchange(a: left, b: randomIndex)
        }
    }
    
    fileprivate func execute(a: Int, b: Int) {
        guard let action = action else {return}
        action(.exchange, (a, b))
    }
    
}
